模拟赛题解/2025.9.18 模拟赛

T1-长城（test）

题面

一个长为 $n$ 的序列 $a$ 被称为墙壁序列当且仅当满足下列条件：

• 对 $1\leq i<n$，有 $a_i\not=a_{i+1}$。
• $a$ 中所有数的异或和为 $0$。

给出 $n$ 和 $m$，求出有多少个长为 $n$ 的墙壁序列 满足 $0\leq a_i<2^m$。答案对 $998244353$ 取模。

$1\leq T\leq 10^5,1\leq n,m\leq10^9$。

题解

注意到一个朴素的思路是第一个数任意选，之后每个数和前一个不同，最后一个固定。

显然会多算最后一位和倒数第二位相同的情况，但此时前 $n-2$ 位 $\text{xor}$ 和为 $0$。

于是我们设 $m$ 固定时，前 $i$ 位和为 $0$ 的情况数为 $f(i)$，得到递推式：

$$f(i)=\begin{cases} 1,\text{ if }i=1\\ 0,\text{ if }i=2\\ 2^m(2^m-1)^{i-2}-(2^m-1)f(i-2),\text{ if }i\geq2 \end{cases}$$

此时有两种做法：

1. 矩阵乘法维护 $f(i)$ 和 $(2^m-1)^i$ 进行转移，矩阵快速幂 $O(n\log n)$。
2. 考虑打表，发现一个神奇性质：若设 $x=2^m-1$

$$f(i)=\begin{cases} x^{i-1},\text{ if }i\bmod 2=1\\ x^{i-1}+(-x)^\frac n2,\text{ if }i\bmod 2=0 \end{cases}$$

复杂度同样是 $O(n\log n)$。

T2-网线（wire）

题面

给定一个字符串 $S$，设其长度为 $n$，每个字符要么是 $\texttt{+}$ 要么是 $\texttt{-}$。

定义一个片段为 $S$ 的一个子串 $S[l,r]$ 满足下面三个条件：

• $l = 1$ 或者 $S_{l-1} \neq S_l$；
• $r = n$ 或者 $S_{r+1} \neq S_r$；
• $S_l = S_{l+1} = \cdots = S_{r-1} = S_r$。

定义一次变换为：选择 $S$ 的两个相邻且长度不同的片段，改变长度较小的那个片段的所有字符为其相反字符。（$\texttt{+}$ 变为 $\texttt{-}$，$\texttt{-}$ 变为 $\texttt{+}$）

现在有 $q$ 次询问，每次询问会给出只包含 $\texttt{+}$ 和 $\texttt{-}$ 并且长度相同的字符串 $S_i, T_i$，请你判断 $S_i$ 是否能够通过若干次变换得到 $T_i$。

$1\leq \sum|S_i|\leq10^6$。

题解

注意到每次操作就是把较短的连续段合并进较长的连续段中，所以我们用链表维护连续段。

如果对于 $T$ 中某一位 $1\leq i<n$，$T_i\not=T_{i+1}$，除非 $T_i=S_i$ 且 $T_{i+1}=S_{i+1}$，否则一定不可能到达。

除此之外，对于某个 $S$ 和 $T$ 相同的连续段，尽量向两边合并显然不劣，因此我们从左向右扫，直接尽量合并。

注意到连续段个数不超过 $n$，并且每次合并减少一个，因此复杂度为 $O(n)$。

T3-里斯（lis）

题面

多组询问，每组给定三个整数 $n$、$a$ 和 $b$。

设 $p=(p_0,p_1,\cdots,p_{n−1})$ 是 $(0,1,\cdots,n−1)$ 的一个排列。若 $P$ 满足以下所有条件， 则称其为墙壁排列：

• $p$ 的最长上升子序列的长度不超过 $2$。
• $p_a=b$。

请计算墙壁排列的个数，答案对 $10^9+7$ 取模。

$1\leq T\leq 10^6,1\leq a,b\leq n\leq5\times10^6$。

题解

考虑 Dilworth 定理，先把题目改成：要求排列 $p$ 的最小上升子序列剖分 $\leq 2$，并且 $p_A = n+1-B$ 的方案数。

对于上升子序列剖分有一个经典算法：每次选择末尾最大的一个可以接下一个元素的子序列接下一个，如果没有就新建一个。 如果按这个流程，则每次都会有一个子序列的末尾为前缀最大值，每个元素比其大才会放进对应的子序列。

所以就把前缀最大值放进一个子序列，别的放进另一个。接下来还需要分析性质： 选定前缀最大值为 $p_{i_1}=v_1, p_{i_2}=v_2,\dots,p_{i_k}=v_k$ 后，至多对应一个合法排列。

存在的条件是：对于所有 $k$ 有 $v_k \geq i_{k+1}-1$。额外性质：所有前缀最大值 $i$ 必然有 $p_i \geq i$，其余位置有 $p_i < i$。

比较难的一步转化：把前缀最大值的直方图画出来，条件等价于直方图的轮廓线一直在 $y=x$ 上方。

若有 $n+1-B \geq A$，则 $A$ 为一个前缀最大值，可以两边做反射容斥；否则考虑逆排列 $q=p^{-1}$，求满足 $LDS$ 长度 $\leq 2$ 且 $q_{n+1-B}=A$ 的 $q$，就化归了。

最终复杂度 $O(n)$。

T4-上课（lesson）

题面

小墙壁在大学里报了两门课，分别在两个不同的教室上课。第 $i$ 门课有 $n_i$ 节，第 $j$ 节的上课时间是 $a_{i,j}$ 到 $b_{i,j}$（不含两端）。保证同一门课的上课时间互不重叠，但是两门课之间的上课时间可能重叠。

小墙壁非常强，只要某节课中的任意短的一段时间范围中（不能为一个时间点），他在上这节课的教室内，他就必定能听懂这节课的内容。然而，他需要 $k$ 的时间从一个教室走到另一个教室。时刻 $0$ 时，他在第一门课的上课教室。小墙壁想问你，通过合理地在两个教室间往返，他最多能够听懂几节课？

$1\leq n\leq3\times10^5,0\leq a_{i,j}\leq b_{i,j}\leq 10^9,1\leq k\leq 10^9$。

题解

将每个 $a_{i,j}, b_{i,j}$ 增加 $0.5$，这样只需要在整数 $\pm \varepsilon$ 的时刻转场即可，可以钦定转场时间为整数。

首先考虑高复杂度 dp。设 $dp_{i,j}$ 为 $j$ 时刻在 $i$ 号教室，之前最多上几节课。 如果上个时刻还在该教室，可以直接转移。但如果刚刚经历转场，直接用 $dp_{3-i, j-k} + 0/1$ 转移可能是错的，因为可能把现在正在上的课算了两遍。

可以用贪心解决：如果之前在教室 $i$ 的最后时刻，现在在上的课已经开始，那不如提早前往教室 $3-i$ 的时间，因为待在教室 $i$ 不能获得更多收益。 所以可以钦定不会在教室 $i$ 上两次同样的课。

如果现在正在上的课开始时间是 $t$，就用 $dp_{3-i, t-1+k} + x + 0/1$ 来转移，其中 $x$ 是在教室 $3-i$ 新听的课数，$0/1$ 表示教室 $i$ 是否在上课（如果不在上课，就无此限制）。

显然 $dp_{i,j}$ 随 $j$ 不减且最多为 $n_1+n_2$，且只有 $dp_{i,j} > dp_{i,j-1}$ 的位置是有用的。
考虑从时间维上扫描线，动态维护目前 $dp_{1,j}, dp_{2,j}$ 的大小及之前的信息。

第二类转移的限制可改为：对于某个 $dp_{i,j}$，如果教室 $3-i$ 在 $j-k$ 时刻在上课，并且这节课在 $t$ 时刻下课，那么 $dp_{i,j}$ 只能在 $\max(j+k, t+1)$ 时刻开始才能贡献到其他状态，否则只要 $j+k$ 时刻就可以。

对于转移中的 $x$，可以拆成目标时刻 $-k$ 前已上课数减去时刻 $j$ 前已上课数，所以只需要记录最大的 $dp_{i,j}$ 减去时刻 $j$ 前课数。

转移方程发生变化只会是以下几种情况之一：

• 一节课开始；
• 一节课结束；
• 一个新的第二类转移被允许；
• $k$ 时刻前一节课开始（因为第二类转移中的 $x$ 会增加一）。

总量是 $O(n)$ 的。用 $\text{priority\_queue}$ 按时间顺序更新转移即可。

另一种做法是尝试从小到大依次二分出 $dp_{i,j} > dp_{i,j-1}$ 的位置，或者直接设 $dp_{i,j,0/1}$ 表示在教室 $i$，时刻 $j$，对面正在上的课是否上过，这些做法也都是可行的。